package InsertSort;


/*
*       插入排序在实现上，需要从后向前进扫描，需要反复将已经排序的元素逐步向后进行移位
*     给新位置流出插入空间。
*
*   插入排序的工作原理是：通过构建有序序列，对于未排序的数据，在已排序的序列中从后向前扫描
*   找到相应的位置进行插入。
*/

import java.util.Arrays;

public class Insert {

    // 这里实现 插入排序 的核心算法
    public static int[] insertSort(int[] arr){
        // 首先需要定义一个循环将数组进行扫描
        // 需要注意的是，这里的 for 循环是要从 1 开始的
        // 这是因为插入排序的原理，是需要将元素 从后向前 进行 扫描 插入的
        for(int i = 1; i < arr.length; i++) {
            // 定义一个 flag 标记
            // 这里的 flag 标记是记录当前 i 下表下的元素
            int flag = arr[i];

            // 在创建出一个指针，用来指向 i 元素的前一个位置
            int j = i - 1;

            // 此时就需要进行循环操作
            // 这次的循环是需要向前进行遍历的
            for(; j >=0; j--) {
                // 在这个 for 循环中来实现核心排序代码
                if(arr[j] > flag) {
                    // 如果前一个位置的元素值大于 当前 i 位置的值
                    // 此时将 j 位置的值赋值给 i(j - 1) (也就是说将大的值向后进行移动)
                    arr[j + 1] = arr[j];
                } else {
                    // 当不满足交换条件时，此时直接跳过即可
                    break;
                }
            }
            // 最后，需要将 flag 中保存的最小值移动到合适的位置

            // 需要注意的是 j-- 在执行完一次 for 循环后才会对数字进行 -- 操作。
            // 对于这里也就会多进行一次递减，使得指向的位置在，目标位置之后
            // 也就是说，这里要将 flag 插入的位置
            // 应该是 j + 1 的 位置
            arr[j + 1] = flag;
        }
        return arr;
    }

    public static void main(String[] args) {
        int[] array = {19,43,2,33,7,8,11,2,90};

        System.out.println(Arrays.toString(insertSort(array)));

    }
}
